#include <string.h>
#include <stdlib.h>
#include "avl.h"

#define MAX(X, Y) X > Y ? X : Y

/* nodes of the tree */
typedef struct _node_t
{
    const char *data;

    struct _node_t *left;
    struct _node_t *right;

    int height;
} node_t;

struct _avl_t
{
    size_t size;
    node_t *root;
};

avl_t *avl_create(char **buffer, size_t *ibuffer, unsigned int nbuffers, size_t maxsize)
{
    avl_t *avl = (avl_t *) malloc(sizeof(avl_t));

    avl->size = 0;
    avl->root = NULL;

    return avl;
}

static void avl_clear_recursive(node_t *node)
{
    if(node == NULL)
        return;

    avl_clear_recursive(node->left);
    avl_clear_recursive(node->right);

    free(node);
}

void avl_destroy(avl_t *avl)
{
    avl_clear_recursive(avl->root);

    free(avl);
}

static int height(node_t *node)
{
    return node == NULL ? -1 : node->height;
}

/* function to balance de tree */
static node_t *single_rotate_with_left(node_t *n2)
{
    node_t *n1;

    n1 = n2->left;
    n2->left = n1->right;
    n1->right = n2;

    n2->height = MAX(height(n2->left), height(n2->right)) + 1;
    n1->height = MAX(height(n1->left), n2->height) + 1;

    return n1;
}

/* function to balance de tree */
static node_t *single_rotate_with_right(node_t *n1)
{
    node_t *n2;

    n2 = n1->right;
    n1->right = n2->left;
    n2->left = n1;

    n1->height = MAX(height(n1->left), height(n1->right)) + 1;
    n2->height = MAX(height(n2->right), n1->height) + 1;

    return n2;
}

/* function to balance de tree */
static node_t *double_rotate_with_left(node_t *n3)
{
    n3->left = single_rotate_with_right(n3->left);

    return single_rotate_with_left(n3);
}

/* function to balance de tree */
static node_t *double_rotate_with_right(node_t *n1)
{
    n1->right = single_rotate_with_left(n1->right);

    return single_rotate_with_right(n1);
}

static node_t *
avl_insert_recursive(node_t *node, const char *data, int *ret)
{
    /* place to store the new data found */
    if(node == NULL)
    {
        node = (node_t *) malloc(sizeof(node_t));

        node->data = data;
        node->height = 0;
        node->left = node->right = NULL;

        *ret = 1;
    }
    /* the new word is lexicographically smaller than the other */
    else if(strcmp(data, node->data) < 0)
    {
        node->left = avl_insert_recursive(node->left, data, ret);
        /* balance if necessary */
        if(height(node->left) - height(node->right) == 2)
        {
            if(strcmp(data, node->left->data) < 0)
                node = single_rotate_with_left(node);
            else
                node = double_rotate_with_left(node);
        }
    }
    /* the new word is lexicographically greater than the other */
    else if(strcmp(data, node->data) > 0)
    {
        node->right = avl_insert_recursive(node->right, data, ret);
        /* balance if necessary */
        if(height(node->right) - height(node->left) == 2)
        {
            if(strcmp(data, node->data) > 0)
                node = single_rotate_with_right(node);
            else
                node = double_rotate_with_right(node);
        }
    }

    /* update height */
    node->height = MAX(height(node->left), height(node->right)) + 1;

    return node;
}

int avl_insert(avl_t *avl, const char *data)
{
    int ret = 0;

    avl->root = avl_insert_recursive(avl->root, data, &ret);

    return ret;
}

